/**
  * @file    :LinkStack.hpp
  * @brief   :
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2023-12-27
*/

#ifndef _STACK_LINKSTACK_H_
#define _STACK_LINKSTACK_H_

#include "iostream"
#include "Stack.hpp"

// 链栈的结点定义
template<typename type>
struct LinkStackNode {

    explicit LinkStackNode(struct LinkStackNode<type> *next = nullptr) : next(next) {}

    explicit LinkStackNode(const type &data, struct LinkStackNode<type> *next = nullptr) : data(data), next(next) {}

    type data;                       // 数据域
    struct LinkStackNode<type> *next;// 指针域
};

template<typename type>
class LinkStack;

template<typename type>
std::ostream &operator<< (std::ostream& out, LinkStack<type> &src);

// 链栈模板类
template<typename type>
class LinkStack : public Stack<type> {

    friend std::ostream &operator<< <>(std::ostream& out, LinkStack<type> &src);

public:
    // 默认构造函数
    LinkStack() : m_top(nullptr) {}

    // 析构函数
    ~LinkStack() {
        Clear();
    }

    // 清空链栈
    bool Clear();

    // 入栈
    virtual bool Push(const type &data);

    // 出栈(保存数据)
    virtual bool Pop(type &data);

    // 出栈(不保存数据)
    virtual bool Pop();

    // 获取栈顶元素
    virtual bool Top(type &data);

    // 判断栈是否为空
    virtual bool IsEmpty();

    // 获取栈的大小
    virtual int Length();

private:
    LinkStackNode<type> *m_top;// 栈顶指针
};

// 清空链栈
template<typename type>
bool LinkStack<type>::Clear() {
    while (m_top != nullptr) {
        LinkStackNode<type> *cur = m_top;
        m_top = m_top->next;

        delete cur;
        cur = nullptr;
    }
    return true;
}

// 入栈
template<typename type>
bool LinkStack<type>::Push(const type &data) {
    auto *newNode = new LinkStackNode<type>(data);
    if (!newNode) {
        return false;
    }

    newNode->next = m_top;
    m_top = newNode;

    return true;
}

// 出栈(保存数据)
template<typename type>
bool LinkStack<type>::Pop(type &data) {
    if (IsEmpty()) {
        return false;
    }

    LinkStackNode<type> *del = m_top;

    data = del->data;
    m_top = del->next;
    
    delete del;
    del = nullptr;

    return true;
}

// 出栈(不保存数据)
template<typename type>
bool LinkStack<type>::Pop() {
    if (IsEmpty()) {
        return false;
    }

    LinkStackNode<type> *del = m_top;

    m_top = del->next;
    
    delete del;
    del = nullptr;

    return true;
}

// 获取栈顶元素
template<typename type>
bool LinkStack<type>::Top(type &data) {
    // 异常处理
    if (IsEmpty()) {
        return false;
    }

    data = m_top->data;

    return true;
}

// 判断栈是否为空
template<typename type>
bool LinkStack<type>::IsEmpty() {
    if (m_top == nullptr) {
        return true;
    }

    return false;
}

// 获取栈的大小
template<typename type>
int LinkStack<type>::Length() {
    int size = 0;
    LinkStackNode<type> *cur = m_top;
    while (cur != nullptr) {
        size++;
        cur = cur->next;
    }

    return size;
}

// 重载 << 运算符
template<typename type>
std::ostream &operator<< (std::ostream& out, LinkStack<type> &src) {
    out << "栈中元素个数: " << src.Length() << std::endl;                  

    LinkStackNode<type>* cur = src.m_top;                                    

    for (int i = 1; cur != NULL; i++) {                                     
        out << cur->data << std::endl;                                      
        cur = cur->next;                                                    
    }

    return out;                   
}

#endif// _STACK_LINKSTACK_H_